The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
Dependency parsers typically utilize a parsing algorithm to find a most-likely parse for a given text, e.g., a sentence. A most-likely parse will identify head-modifier pairs for each word in the text. Each word in the text will be identified as a “modifier” for a “head,” which is a different word in the text (or a “null” token such as that identifying a beginning of a sentence). Each word in the text, however, does not necessarily operate as a “head” of another word. As the number of words in a text increases, the amount of time necessary to compute the most-likely parse may increase exponentially. For example only, a text having a length n can have a first-order index set of n2 elements, where each index may be identified as (h, m) where h has a value of {0, . . . n}, m has a value of {0, . . . n} and h≠m. In this example, if the parsing algorithm analyzes and scores each index individually, the number of operations may be so computationally expensive as to be prohibitive. Additionally, for higher-order dependency parsing, these problems are exacerbated as the number of computations is even larger. An efficient parsing technique that reduces the number of computations necessary while maintaining an acceptable level of accuracy would be desirable.